\documentclass{acm_proc_article-sp}

\usepackage[utf8]{inputenc}
\usepackage{biblatex}

\bibstyle{abbrv}
\bibliography{pbib}

\begin{document}

\title{An Effective Pedagogical Module for Booth's Multiplication Algorithm}

\numberofauthors{3}
\author{
    \alignauthor
    Dr. David
Furcy\\
       \affaddr{University of Wisconsin Oshkosh}\\
       \affaddr{800 Algoma Boulevard}\\
       \affaddr{Oshkosh, WI 54901}\\
       \email{furcyd@uwosh.edu}
    \alignauthor
    Christopher W.
Jenkins\\
       \affaddr{Trinity University}\\
       \affaddr{One Trinity Place}\\
       \affaddr{San Antonio, TX 78212}\\
       \email{cjenkin1@trinity.edu}
    \alignauthor
    Adam D.
Voss\\
       \affaddr{Luther College}\\
       \affaddr{700 College Drive}\\
       \affaddr{Decorah, IA 52101}\\
       \email{vossad01@luther.edu}
}

\maketitle

\begin{abstract}
//TODO abstract
\end{abstract}

\section{Introduction}
In almost all computer design curricula, there is some discussion of the process by which binary numbers are multiplied at the machine level.
However, there is variation in how this subject is covered, for example over which methods of multiplication to discuss, how negative numbers are dealt with, how efficiency is achieved, and how much hardware-level detail should be included in the explanation of the process.
Additionally, there is always a trade-off between the time spent in class on individual subjects and the number of subjects covered.
Because of this, the professor may choose to spend less class time discussing methods for binary multiplication in order to cover other topics.

We propose that an effective, self-contained learning module available online could resolve these issues.
The module we designed for this purpose is composed of an online text resource (``hyper-textbook'' or ``hypertext'') for the subject and a visualization of a multiplication algorithm.
We used a constructivist model for the approach of the hyper-textbook, beginning with the ``pencil and paper'' algorithm familiar to most students and demonstrating by successive modifications how it can be mapped onto hardware.
For the visualization, since current research in the field of algorithm visualizations suggests that the most important aspect of an effective algorithm visualization is the level of user engagement\cite{tnaps:visengage}, we developed questions and exercises with its use.
We use the engagement taxonomy developed by the Innovation and Technology in Computer Science Education Working Group in 2002 (ITiCSE02) to describe the different components of our visualization.

An effective method for the multiplication of signed binary values was introduced by Andrew Booth in 1951, involving the comparison of pairs of bits as the algorithm is executed.
At its heart lies the observation that a sum of powers of two $2^n + 2^{n-1} + ...
+ 2^{n-k}$ is equal to $2^{n+1} - 2^{n-k}$.
The most important contribution of this method is that little hardware or processing is needed to derive the correct result for all cases\cite{booth}.
Another advantage of this method is that, in many cases, it can be significantly faster than other methods of binary multiplication due as it reduces the number of arithmetic operations.\cite{text1}
For its use of mathematical insight into a problem to meet design requirements, we believe that Booth's algorithm is of educational value and we therefore chose to use it in our hypertext and visualization.
However, while some textbooks include a discussion of Booth's algorithm in their discussion of binary multiplication, it is not universally discussed in textbooks, and furthermore because of the time constraints mentioned above a professor may choose to gloss over or elide the topic completely.

Many textbooks include figures depicting the execution of the binary multiplication algorithm along with its description\cite{needsCitation}.
Such figures can be considered a kind of algorithm visualization, and as such lack an effective form of engagement other than a primitive ``Viewing''.
It would be beneficial if, for example, the student were able to view multiple visualizations with hand-picked values to reinforce their understanding of the algorithm.
For this reason we have chosen to include with our hyper-textbook an algorithm visualization, developed for the Java Hosted Algorithm Visualization Environment (JHAVÉ)\cite{JHAVE}.
We made this decision to satisfy three features we felt were required of our visualization in order to make it effective.
First, JHAVÉ allows for an interactive and step-by-step demonstration of the running algorithm, which we felt the student would prefer over a static diagram.
Second, the JHAVÉ framework provides tools for automated assessment in the form of questions generated during the visualization.
Finally, through the use of the framework's ``input generator'' feature, we were both able to allow students to create their own test data for the visualization and to create additional exercises requiring the student to input data which will cause specific results during the execution of the algorithm or on its completion.
These three motivations are directly correlated to three levels of the engagement taxonomy defined by ITiCSE02: ``Viewing'', ``Responding'' and ``Changing''.

\section{Related Work}
Constructivism, which holds that students ``[build] recursively on [prior] knowledge'', is the dominant theory of learning in the field of education.
It is supposed that constructivism is a more effective educational paradigm because it anticipates the idiosyncratic process by which students acquire knowledge\cite{constr}.
Following this, it is important that educational material anticipate students' ``effective model'' for a subject first and then guide them to a better understanding.
Critically, constructivism also gives an explanation for the ineffectiveness of passive learning, as by definition it considers education an active process\cite{constr}.

Ever since the first algorithm visualization, the 1981 video ``Sorting out sorting'' by Ronald Baeker\cite{sorting}, AVs have played a role in the discussion on computer science education.
Research in the field of the effectiveness of algorithm visualizations has shown that, while AVs are almost universally deemed by educators to have educational value\cite{tnaps:visengage}, there is no evidence to support the claim that an AV by itself will improve a student's understanding of an algorithm.
Instead, the research shows that in order for AVs to be effective, they must actively engage the student\cite{tnaps:visengage}.
To better describe the ways in which AVs engage the student, Naps et al.
developed an ``Engagement Taxonomy''.
The three levels which are most relevant to our research are listed below.\cite{tnaps:visengage}

\begin{itemize}

\item \textbf{Viewing} is considered the ``core form of engagement'', without which no visualization is possible.
While viewing is considered the most passive form of engagement, it can be made more active if the learner is allowed to control the pace of the visualization and has access to multiple screens or sources of information.

\item \textbf{Responding} involves having the student provide responses to questions about the algorithm which is visualized.
It is considered to be a higher level of engagement since it requires that the student first `view' the visualization and comprehend enough of the depicted algorithm before are able to provide an answer.

\item \textbf{Changing} involves allowing the student to modify parts of the visualization.
The most common activity of this level is visualizing the given algorithm with values input by the student, generally combined with questions about the algorithm's behavior when encountering certain cases.

\end{itemize}

Current research has brought into question the effectiveness of pop-up questions in algorithm visualizations.
Rhodes et al.
have shown that while questions which are responsive or predictive in nature can improve overall performance and comprehension, their effectiveness is mostly determined by whether immediate feedback is given to students when they submit an incorrect answer.
Students exposed to questions of these types without feedback performed on average slightly worse than students not exposed to questions.
One reason suggested for this result was that pop-up questions of these kinds tested students at a lower ``procedural'' level and not a higher ``conceptual'' level.\cite{intquest}
At the time of this research, JHAVÉ did not support question feedback, so we chose to focus our efforts on developing a richer question schema, designed to test the student on multiple levels with varying question formats.

\section{Implementation of the Visualization}
In our design and implementation of the visualization for Booth's algorithm, our primary consideration was for active user engagement.
Prior research by ITiSCE02 suggests that this is the most important aspect for an effective visualization.\cite{tnaps:visengage}
Organized by level of engagement, our visualization supports the following: at the ``Viewing'' level, it includes graphical representations of registers and binary arithmetic, text annotations and pseudo code
 display; at the level of ``Responding'', we include pop-up questions designed to check the user's basic understanding of the algorithm; and at the ``Changing'' level, we designed a set of exercises in which the user is given a constraint or set of constraints on the behavior of the executing algorithm and must provide data to meet that constraint.
In the standard use of the visualization, we also allow the user to choose their own input data or use the provided default values.

JHAVÉ was chosen as the system to develop a visualization for Booth's algorithm, as it supported these features and was in fact designed with these three levels of engagement in mind.\cite{JHAVE}

\subsection{Standard Mode}
Our visualization was designed so that the user would step through each of the major operations of Booth's multiplication algorithm.
For each of these operations, there is a corresponding text annotation at the top of the screen and highlighted line of pseudo code in the right pane.
For addition and subtraction operations, we provide space on the right side of the screen, designated in the visualization as ``Math/ALU'', to reinforce binary arithmetic.
We also chose to keep a running history of the execution of the algorithm on screen for the user's reference.
Registers in history are grayed out so as to distinguish them from the registers which are active in the algorithm.
\subsection{Questions}
JHAVÉ also supports the inclusion of questions which appear during the visualization of the algorithm.
These were created to test the user on multiple levels of understanding, as defined by Bloom's taxonomy(NEEDS JUSTIFICATION).
These questions are strategically placed and appear approximately once every -- snapshots to ensure the user in engaged at important moments of the algorithm's execution.
To prevent boredom in the user and predictability in the questions, multiple presentations of the same ``type'' of question are used.
Questions are in the following formats: true or false, fill in the blank, multiple choice and multiple selection.
\subsection{Exercises}%potentially something subject to change.
Finally, through the use of input generators to JHAVÉ, we included several exercises to go along with the visualization.
The user is given certain constraints, in the form of an expected behavior in or result of the algorithm and is asked to provide data which will meet those constraints.
There are -- exercises available to the student.
Exercise modes will not include questions, but instead a status message accepting or rejecting the user's input at the end of the visualization.

\printbibliography

\balancecolumns
\end{document}
